import java.util.Random;

public class test215 {
    Random random = new Random();

    int AdjustArray(int a[], int l, int r){
        int i = l;
        int j = r;
        int x = a[i];
        while(i < j){
            while (i < j && a[j] >=x)
                j--;
            if(i<j){
                a[i]=a[j];
                i++;
            }

            while (i < j && a[i]<x)
                i++;
            if(i<j){
                a[j]=a[i];
                j--;
            }
        }
        a[i] = x;
        return i;
    }

    void quick_sort(int a[],int l,int r){
       if(l<r) {
           int i = AdjustArray(a, l, r);
           quick_sort(a, l, i - 1);
           quick_sort(a, i + 1, r);
       }
    }

    void quick_sort_sum(int a[],int l,int r){
        if(l<r) {
        int i = l;
        int j = r;
        int x = a[i];
        while(i<j){
            while(i<j && a[j]>=x)
                j--;
            if(i<j){
                a[i]=a[j];
                i++;
            }
            while(i<j && a[i]<x)
                i++;
            if(i<j){
                a[j]=a[i];
                j--;
            }
        }
        a[i]=x;
            quick_sort_sum(a, l, i);
            quick_sort_sum(a, i, r);
        }
    }
//    public int findKthLargest(int[] nums, int k) {

//        if (nums.length==1)
//            return nums[0];
//        int tmp = Integer.MIN_VALUE;

//        for(int i = 1;i < nums.length;i ++){
//            if(nums[i]<nums[i-1]) {
//                tmp = nums[i];
//                nums[i] = nums[i - 1];
//                nums[i - 1] = tmp;
//            }
//        }

//        for(int i=1;i<nums.length;i++){//从数组的第二个元素到数组的最后一个元素依次取出来插入到它前面的数的合适位置中
//            int insertNumber=nums[i];//将要插入的数据赋值给变量insertNumber
//            int j=i-1;
//            while(j>=0&&insertNumber<nums[j]){//要插入的元素小于第j个元素
//                nums[j+1]=nums[j];//第j个元素向后移动
//                --j;//比较插入数据和r[j]的大小，直到j为0
//            }
//            nums[j+1]=insertNumber;//退出while循环，即插入的数据已经不小于r[j]了，这时插入数据插入到r[j]后面
//        }
//        return nums[nums.length-k];


    //官方快速排序
    public int findKthLargest(int[] nums, int k) {
            return quickSelect(nums, 0, nums.length - 1, nums.length - k);
            //快速排序参数：数组，最左边的值，最右边的值，倒数第k个数
        }

        public int quickSelect(int[] a, int l, int r, int index) {
            int q = randomPartition(a, l, r);//随机取一个值，取值为[l,r],q为随机数下标
            if (q == index) {
                return a[q];
            } else {
                return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
            }
        }

        public int randomPartition(int[] a, int l, int r) {
            int i = random.nextInt(r - l + 1) + l;//[l,r]
            //random.nextInt(r - l ) + l --> [l,r)
            swap(a, i, r);//交换i下标与最右边的下标的值
            return partition(a, l, r);//这里的r代表的值是随机数，返回排序后随机数的下标
        }

        public int partition(int[] a, int l, int r) {
            int x = a[r], i = l - 1;//X就是随机数
            for (int j = l; j < r; ++j) {
                if (a[j] <= x) {//如果小于随机值，那么交换i+1,j两者
                    swap(a, ++i, j);
                }
            }
            swap(a, i + 1, r);//交换回来，小于这个随机数的全部在左边，大于这个随机数的全部在右边
            return i + 1;
        }

        public void swap(int[] a, int i, int j){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
